import java.util.Arrays;

public class HeapSort {
    private int[] arr;

    public HeapSort(int[] arr) {
        this.arr = arr;
    }
    public void sort(){
        int len = arr.length-1;
        int beginIndex = (len-1)>>1;
        for(int i=beginIndex;i>=0;i++){
            maxHeapify(i,len);
        }
        for(int i=len;i>0;i--){
            swap(0,i);
            maxHeapify(0,i-1);
        }
    }

    private void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private void maxHeapify(int index, int len) {
        int li=(index<<1)+1;
        int ri = li+1;
        int cMax=li;
        if(li>len) return;
        if(ri<=len && arr[ri]>arr[li])
            cMax=ri;
        if(arr[cMax]>arr[index]){
            swap(cMax,index);
            maxHeapify(cMax,len);
        }
    }


    public static void main(String[] args) {
        int[] nums = new int[]{3,2,1,5,6,4};
        new HeapSort(nums).sort();
        System.out.println(Arrays.toString(nums));
    }
}
